#include "grafo.h"
#include "common.h"
#include <iostream>
#include <iterator>

/*======================================================================
	Algoritmo exacto
------------------------------------------------------------------------

	Se utiliza backtracking como algoritmo exacto.
	Para mejorar su runtime, se utilizo un algoritmo del estilo de
	branch and bound: Se da una cota inicial del problema 
	(obtenida del libro de Gross y Yellen) y se utiliza la siguiente
	poda: Si el conjunto de nodos que estamos mirando ya tiene igual
	o mayor cantidad del nodos que el minimo hasta ahora, se detiene
	la propagacion.
	
======================================================================*/

static vint cubierto, dominante, minimo;
static unsigned int cota;
using namespace std;

static void backtrack(const Grafo & grafo, const vint & componente, 
			unsigned int cubiertos, int previo){	
	if(cota <= dominante.size()) return;

	if(cubiertos == componente.size()){
		if(dominante.size() <= cota){
			cota = dominante.size();
			minimo = dominante;
		}
		return;
	}
	
	int nodosCompo = componente.size();
	for(int i = previo+1; i < nodosCompo; i++){
		int nuevos = 0,nodo = componente[i];

		dominante.push_back(nodo);
		const vint & vecinos = grafo.vecinos(nodo);

		if(!cubierto[nodo]) nuevos++;
		cubierto[nodo]++;

		for(unsigned int j = 0; j < vecinos.size(); j++){	
			int vecino = vecinos[j];
			if(!cubierto[vecino]){
				nuevos++;
			}
			cubierto[vecino]++;
		}
		
		if(nuevos > 0)
			backtrack(grafo,componente,cubiertos+nuevos,i);
		
		cubierto[nodo]--;
		dominante.pop_back();
		for(unsigned int j = 0; j < vecinos.size(); j++){
			cubierto[vecinos[j]]--;
		}
	}
}

vint exacto(const Grafo & grafo, const vint & componente){		
		cubierto.clear(); cubierto.resize(grafo.nodos());

		fill(cubierto.begin(),cubierto.end(),0);
		minimo.clear(); dominante.clear();
		
		//Cota dada por el libro de Gross y Yellen
		cota = 1+(1+componente.size())/2;
		backtrack(grafo,componente,0,-1);

		return minimo;
}
